#include <iostream>
#include <vector>
#include <queue>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
};

int tree_depth(TreeNode* root)
{
    if (!root) return 0;

    std::queue<TreeNode*> q;
    q.push(root);
    int depth = 0;

    while (!q.empty())
    {
        int sz = q.size();
        depth++;
        for (int i = 0; i < sz; i++)
        {
            TreeNode* node = q.front(); 
            q.pop();
            if (node->left) 
                q.push(node->left);
            if (node->right) 
                q.push(node->right);
        }
        // 判空为什么无处不在呢？？？
    }
    return depth;
}

TreeNode* tree_builder(std::vector<int>&v)
{
    int n = v.size();
    if (!n)             return nullptr;

    // 但是我还是忘记他应该怎么写了！！！！！！！！
    // 依旧是层序遍历基础不扎实？？？

    std::queue<TreeNode*>q;

    TreeNode*root = new TreeNode;
    root->val = v[0];
    root->left = nullptr;
    root->right = nullptr;
    int count = 1;

    q.push(root);
    while (count < n&&!q.empty())
    {
        int temp = q.size();    

        while (temp--)
        {
            
            // 取出队列中的首元素
            TreeNode*to_add = q.front();
            q.pop();

            if (count<n&&v[count-1]!=-1)
            {
                // 创建新节点
                TreeNode*node = new TreeNode;
                node->val = v[count-1];
                node->left = nullptr;
                node->right = nullptr;

                // 让待追加节点的左节点试图赋值为新节点
                to_add->left = node;

                // 让他继续被等待追加
                q.push(node);
            }
            count ++;

            if (count<n&&v[count-1]!=-1)
            {
                TreeNode*node = new TreeNode;
                node->val = v[count-1];
                node->left = nullptr;
                node->right = nullptr;
                to_add->right = node;
                q.push(node);
            }
            count++;
        }
    }
    return root;
}

int main()
{
    std::vector<int>v = {3,9,20,-1,-1,15,7};
    TreeNode*root = tree_builder(v);

    std::cout<<tree_depth(root)<<"\n";
    return 0;
}